Frequently, the size of a video or other digital image must be resized for a particular application. For example, a digital image may need to be reduced or enlarged to fit within a certain area in a document. Alternatively, an automated process may require a series of video images of varying sizes to be enlarged or reduced to a fixed size.
Enlarging or expanding a video image typically involves repeating pixels in a sampled video image. Expanding the dimensional format or size of a video image typically does not involve many problems. However, reducing the size of an image often induces noise such as aliasing frequencies which are added to the synthesized, reduced image. For example, lines as artifacts can be created within an image by resampling the image. Prior techniques for eliminating such aliasing frequencies include finite impulse response (FIR) and infinite impulse response (IIR) filtering to remove this noise. A problem with such filtering techniques are that they are less than optimally effective or require significant processing time.
One solution for reducing errors or noise in image resizing involves interpolation. As is known, interpolation is the process of estimating the intermediate values of a continuous event from discrete samples, such as discrete pixels in a digital image. Interpolation has been used to magnify or reduce digital images. Since digital images often involve large amounts of data, efficient interpolation methods are required.
One efficient interpolation method is the cubic convolution interpolation method, which is described, for example, in S. Park, "Image Reconstruction By Parametric Cubic Convolution," Computer Vision, Graphics and Image Processing, 23:258-272, and R. Keys, "Cubic Convolution Interpolation For Digital Image Processing," IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-29, No. 6, December, 1981. Cubic convolution interpolation methods are useful in image processing, and provide accuracy which is better than linear interpolation, but less than cubic spline methods, while still being capable of being efficiently performed on a computer.
As is known, a fundamental property of all interpolation functions is that they must coincide with the sampled data at the interpolation nodes or sample points. Considering only the x-axis dimension of a two-dimensional image, if f is a sampled function, such as one line of pixels in a digital image, and if C is the corresponding interpolation fuinction, then C(x.sub.p)=f(x.sub.p) whenever x.sub.p is at an interpolation node (i.e., at a pixel point). While interpolation of a one-dimensional function is described below, interpolation in two dimensions is readily accomplished by performing the one-dimensional interpolation in each dimension, as noted in the Keys article.
For equally spaced data, such as pixels in the image line, many interpolation functions can be written in the form of ##EQU1## where h represents the sampling increment, the x.sub.k 's are the interpolation points, k is the interpolation kernel, and C is the interpolation function. The w.sub.p 's are parameters which depend upon the sampled data, and are selected so that the interpolation condition C(x.sub.p)=f(x.sub.p) is true for each x.sub.p. Typically, w.sub.j corresponds to the input or sampled pixel values in the image.
The cubic convolution interpolation kernel k is composed of piecewise cubic polynomials defined on sub-intervals within a given interval, e.g., (-2, 2), while the kernel has a value of 0 outside of the interval. On the interval (-2, 2), four sub-intervals, (-2, -1), (-1, 0), (0, 1), and (1, 2) exist, and thus only four data points or samples are used to evaluate the interpolation function under equation (1). Additionally, the interpolation kernel must be symmetric. Thus, the interpolation kernel k becomes: EQU k(z)=a.sub.0 +a.sub.1 .vertline.z.vertline.+a.sub.2 .vertline.z*z.vertline.+a.sub.3 .vertline.z*z*z.vertline., if 0&lt;.vertline.z.vertline.&lt;1; EQU k(z)=b.sub.0 +b.sub.1 .vertline.z.vertline.+b.sub.2 .vertline.z*z.vertline.+b.sub.3 .vertline.z*z*z.vertline., if 1&lt;.vertline.z.vertline.&lt;2; EQU k(z)=0, if .vertline.z.vertline.&gt;2; (2) EQU k(0)=1; EQU k(z)=0, if z is an integer.
Since h is the sampling increment, the difference between the interpolation points x.sub.j and x.sub.p is (j-p)h. Therefore, substituting x.sub.j for x in Equation (1), and selecting four samples on the interval (-2, 2), the following equation results: ##EQU2##
The domain of the sampled function f(x) is restricted to a finite interval, and thus boundary conditions are necessary. Considering the interval (0, 1), the values outside of the interval are considered, i.e., -1 and 2. As a result, the summation under equation (3) extends from p=-1 to p=2.
Because k(j-p) is 0 unless j=p, the right-hand side of Equation (3) reduces to w.sub.p, since the interpolation condition requires that C(x.sub.p)=f(x.sub.p). In addition to being 0 or 1 at the interpolation points, the interpolation kernel k must be continuous and have a continuous first derivative on the intervals (-2, -1), (-1, 0), (0, 1), and (1, 2). In other words, the interpolation kernel must be connected with the smoothness of the function k(z). Thus, k(z) must be of the class C.sup.1 (Re). As a result, four equations for the coefficients a.sub.0 through a.sub.3 and b.sub.0 through b.sub.3 in Equation (2) above exists, and three equations result from the fact that the first derivative of the interpolation kernel is continuous at the points 0, 1, and 2. However, eight unknown coefficients exist. As a result, an eighth equation is necessary to obtain a unique solution.
Assuming that f(x) has several orders of continuous derivatives so that Taylor's theorem applies, we then assume that the cubic convolution interpolation function and the Taylor series expansion for f(x) agree for as many terms as possible. Therefore, letting b.sub.3 =u, the remaining seven coefficients can be determined in terms of u from the seven equations as follows: EQU k(z)=1-(u+3).vertline.z*z.vertline.+(u+2).vertline.z*z*z.vertline., if 0&lt;.vertline.z.vertline.&lt;1; EQU k(z)=-4+8u.vertline.z.vertline.-5u.vertline.z*z.vertline.+u.vertline.z*z*z. vertline., if 1&lt;.vertline.z.vertline.&lt;2; (4) EQU k(z)=0, otherwise.
If the image is to be transformed within minimum alteration, i.e., minimum interpolation error, u is derived from the first terms of the Taylor series expansion of the original sampling function f(x). The Keys article proposes a solution to Equation (4) where u=-1/2, which achieves third-order precision. In other words, the interpolation error goes to 0 uniformly at a rate proportional to the cube of the sampling increment.
Overall, the cubic convolution interpolation method transforms a series of discrete samples into a continuous function. From the continuous function, the image can be resized. However, multiple resizing techniques are available. Additionally, the cubic convolution interpolation method is subject to initial assumptions which affect the resulting continuous function.